Тастатура
| време | меморија | улаз | излаз |
|---|---|---|---|
| 0,7 s | 64 Mb | стандардни излаз | стандардни улаз |
На телевизорима се користе тастатуре на екранима које омогућавају да се текст унесе само коришћењем пет тастера на даљинском управљачу – четири стрелице и тастера ОК. Тастатура је подељена у правоугаону мрежу квадратића, при чему се неки “тастери” протежу преко већег броја квадратића. Пример такве тастатуре је приказан на слици.
Курсор се увек налази изнад једног квадратића. Када се притисне тастер ОК на текст се дописује карактер који пише на том квадратићу. Када се притисне једна од четири стрелице, не прелази се увек на следећи квадратић, већ се прелази на први квадратић у смеру стрелице на ком није написан исти карактер као и на полазном квадратићу. Ако такав квадратић не постоји, курсор се не помера.
На пример, ако се притисне стрелица на десно док је курсор на
квадратићу A у горњем левом углу тастатуре (на позицији
\((0, 0)\)), наредни квадратић на коме
такође пише A се прескаче и долази се на први квадратић на
коме пише B (на позицији \((0,
2)\)). Ако се притисне стрелица на доле, прелази се на квадратић
на коме пише G (на позицији \((1,
0)\)). Ако се притисне стрелица на горе или на лево, курсор се не
помера.
Карактери на тастатури се не понављају – сваком карактеру одговара
највише један “тастер”, али он може бити састављен од више квадратића и
не мора бити правоугаоног облика. Тастататура обавезно садржи и тастер
Enter који је означен карактером * који је
потребно притиснути на крају уноса текста.
Напиши програм који одређује најмањи број притисака тастера потребних да се откуца дати текст.
Улаз
Са стандардног улаза се учитавају димензије правоугаоне мреже \(v \times k\) (\(1 \leq v, k \leq 50\)). Након тога се уноси матрица карактера која описује тастатуру. На крају се уноси линија текста коју је потребно откуцати (она садржи највише \(10~000\) карактера). Сви карактери у тексту сигурно постоје на тастатури.
Излаз
На стандардни излаз исписати најмањи број притисака тастера помоћу којих се може откуцати тражени текст.
Пример 1
Улаз
4 7 ABCDEFG HIJKLMN OPQRSTU VWXYZ** CONTEST
Излаз
30
Пример 2
Улаз
2 4 AABB DCC* BCDA
Излаз
12
Објашњење
Један редослед притискања тастера је десно OK доле ОК лево ОК горе ОК десно доле десно ОК.
Морате бити улоговани како бисте послали задатак на евалуацију.